package com.yxp.offer;

/**
 * @author : yang.xp
 * @date : 2021/9/4 9:24
 * @description : 剑指 Offer 39. 数组中出现次数超过一半的数字
 * <p>
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 */
public class Problem39 {

    public static void main(String[] args) {
        Problem39 problem39 = new Problem39();
        problem39.majorityElement(new int[]{1, 2, 3, 2, 2, 2, 5, 4, 2});
    }

    // 因为超过了一半，所以财大气粗，就算是所有的不同的数跟2抵消，还能剩下n个2
    public int majorityElement(int[] nums) {
        int res = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                res = nums[i];
                count++;
            } else {
                if (res == nums[i]) {
                    count++;
                } else {
                    count--;
                }
            }

        }
        return res;
    }
}
